
//遍历
function display(node){
    while( node != null ){
        console.log(node.value)
        node = node.next;
    }
}
display(linkList);
console.log("<===========================")

//1、头插方式使链表反转
function reverse( linkList ){
   //尾插改头插，链表进行反转
   let reverseHeader = null;
   let p = null;
   while( linkList != null ){
     //采用头插的方式创建一个新的链表.
     p = linkList;  
     linkList = linkList.next;
     if( reverseHeader == null ){
        p.next = null;
        reverseHeader = p;
        continue;
     }
     p.next = reverseHeader;
     reverseHeader = p;
   }
   return reverseHeader;
}
let reverseHeader = reverse(linkList);
console.log("reverseHeader: ");
display(reverseHeader);


//2、尾递归方式使链表反转
function reverseByRecursion( linkList ){
    if( linkList.next != null ){
      let result = reverseByRecursion(linkList.next);
      let last = result.last;
      console.log(last.value)
      last.next = linkList;
      linkList.next = null;
      return {
          header: result.header,
          last: linkList
      }  
    }
    return {
        header: linkList,
        last: linkList
    };
}

let result = reverseByRecursion( reverseHeader );
console.log("================reverseByRecursion====================")
display(result.header);
